# 迷宫： 由于我们不知道迷宫的构造，所以没法用bfs，只能用dfs

clear()
pet_the_piggy()
from utils import *

set_world_size(6)

l = get_world_size()

# 用于顺时针遍历的四个方向
DIRS = [North, East, South, West]
def get_next_pos(cur_pos, dir):
    x, y = cur_pos
    if dir == North:
        return (x, y + 1)
    elif dir == East:
        return (x + 1, y)
    elif dir == South:
        return (x, y - 1)
    else:
        return (x - 1, y)
substance = get_world_size() * 2**(num_unlocked(Unlocks.Mazes) - 1)


def dfs_single(regen_maze_times=0):
    # '''regen_maze_times: 迷宫重生次数'''
    start_pos = get_pos()

    stack = []
    visited = set()

    stack.append(start_pos)
    visited.add(start_pos)
    while 1:
        cur_pos = stack[-1]
        
        if get_entity_type() == Entities.Treasure:
            if regen_maze_times > 0:
                regen_maze_times -= 1
                use_item(Items.Weird_Substance, substance)
                dfs_single(regen_maze_times)
                return
            else:
                harvest()
                return True
        
        found_next_pos = False
        for dir in DIRS:
            next_pos = get_next_pos(cur_pos, dir)
            # 如果下个节点能走,即不是墙壁不是来路并且没有访问过
            if can_move(dir) and next_pos != cur_pos and not next_pos in visited:
                move(dir) # 移动
                stack.append(next_pos)
                visited.add(next_pos)
                found_next_pos = True
                break
        # 如果所有方向都尝试过, 则回溯
        if not found_next_pos:
            stack.pop() # 回溯
            x,y = stack[-1]
            goto(l,x,y)

while 1:    
    gen_maze_fullsize()
    dfs_single(20)